package s12_经典算法.a9_马踏棋盘算法;


import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by 西瓜瓜
 * Date :2022/2/27
 * Description :
 * Version :1.0
 * <p>
 * 马踏棋盘算法
 */
public class HorseChessboard {

    /**
     * 棋盘的列
     */
    private static int X;
    /**
     * 棋盘的行
     */
    private static int Y;
    /**
     * 标记棋盘的各个位置是否被访问过
     */
    private static boolean[] visited;
    /**
     * 标记是否棋盘的所有位置都被访问过
     */
    private static boolean finished;

    /**
     * 马踏棋盘算法
     *
     * @param chessboard 棋盘
     * @param row        马儿当前位置的行 从0开始
     * @param col        马儿当前位置的列 从0开始
     * @param step       第几步 初始位置从1开始
     */
    public void traversalChessBoard(int[][] chessboard, int row, int col, int step) {
        chessboard[row][col] = step;
        visited[row * X + col] = true; // 标记该位置已经访问
        // 获取当前位置可以走的下一个位置的集合
        List<Point> ps = next(new Point(col, row));
        sort(ps);
        // 遍历ps
        while (!ps.isEmpty()) {
            // 取出下一个可以走的位置
            Point p = ps.remove(0);
            // 判断该点是否已经访问过
            if (!visited[p.y * X + p.x]) {
                // 说明还没有访问过
                traversalChessBoard(chessboard, p.y, p.x, step + 1);
            }
        }

        if ((step < X * Y) && !finished) {
            chessboard[row][col] = 0;
            visited[row * X + col] = false; // 标记该位置未访问
        } else {
            finished = true;
        }

    }

    /**
     * 根据当前位置，计算马儿还能走哪些位置，并一并放入到集合中，最多有8个位置
     *
     * @param curPoint
     * @return
     */
    public List<Point> next(Point curPoint) {
        List<Point> list = new ArrayList<>();

        Point p1 = new Point();
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            list.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            list.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            list.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            list.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            list.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            list.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            list.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            list.add(new Point(p1));
        }

        return list;
    }

    /**
     * 对ps进行非递减排序
     * @param ps
     */
    public void sort(List<Point> ps) {
        ps.sort((o1, o2) -> {
            List<Point> o1List = next(o1);
            List<Point> o2List = next(o2);
            return o1List.size() - o2List.size();
        });
    }


    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 8; // 马儿初始位置的行
        int col = 1; // 马儿初始位置的列
        // 创建棋盘
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];

        HorseChessboard horseChessboard = new HorseChessboard();
        horseChessboard.traversalChessBoard(chessboard, row - 1, col - 1, 1);

        for (int[] rows : chessboard) {
            System.out.println(Arrays.toString(rows));
        }
    }
}
